#ifndef INTERPOLATION
#define INTERPOLATION

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

class Function
{
public:
    virtual double operator()(double x)
    {
        return 0;
    }
};

class Newton
{
private:
    int n;
    vector<double> x, y, z;

public:
    //初始化
    Newton(int _n, vector<double> _x, vector<double> _y) : n(_n), x(_x), y(_y) {}
    // Newton插值
    void Newtonpolation()
    {
        vector<double> t;
        for (int i = 0; i <= n; i++)
        {
            t.push_back(y[i]);
            for (int j = 1; j <= i; j++)
            {
                double value;
                int p = i * (i + 1) / 2 + j - 1;
                int q = i * (i - 1) / 2 + j - 1;
                value = (t[p] - t[q]) / (x[i] - x[i - j]);
                t.push_back(value);
            }
        }
        for (int i = 0; i <= n; i++)
        {
            z.push_back(t[i * (i + 3) / 2]);
        }
    }
    //输出系数
    void printcoefficient()
    {
        for (int i = 0; i <= n; i++)
        {
            printf("%.6f ", z[i]);
        }
        printf("\n");
    }
    //输出多项式
    void printpolynomial()
    {
        for (int i = 0; i <= n; i++)
        {
            printf("%f", z[i]);
            for (int j = 0; j < i; j++)
            {
                printf("*(x");
                if (x[j] < 0)
                    printf("+");
                printf("%.2f)", -x[j]);
            }
            if (i < n && z[i + 1] >= 0)
            {
                printf("+");
            }
        }
        printf("\n");
    }
};

class Hermite
{
private:
    int n;
    vector<double> x, y, z;

public:
    //初始化
    Hermite(int _n, vector<double> _x, vector<double> _y) : n(_n), x(_x), y(_y) {}
    // Hermite插值
    void Hermitepolation()
    {
        vector<double> t;
        for (int i = 0; i <= n; i++)
        {
            t.push_back(y[i]);
            int zw;
            for (int j = 0; j <= i; j++)
            {
                if (x[j] == x[i])
                {
                    zw = j;
                    break;
                }
            }
            if (zw != i)
            {
                t.pop_back();
                t.push_back(y[zw]);
            }
            for (int j = 1; j <= i; j++)
            {
                double value;
                if (x[i] == x[i - j])
                {
                    value = y[zw + j];
                    for (int k = 1; k <= j; k++)
                        value /= k;
                }
                else
                {
                    int p = i * (i + 1) / 2 + j - 1;
                    int q = i * (i - 1) / 2 + j - 1;
                    value = (t[p] - t[q]) / (x[i] - x[i - j]);
                }
                t.push_back(value);
            }
        }
        for (int i = 0; i <= n; i++)
        {
            z.push_back(t[i * (i + 3) / 2]);
        }
    }
    //输出系数
    void printcoefficient()
    {
        for (int i = 0; i <= n; i++)
        {
            printf("%f ", z[i]);
        }
        printf("\n");
    }
    //输出多项式
    void printpolynomial()
    {
        for (int i = 0; i <= n; i++)
        {
            printf("%f", z[i]);
            for (int j = 0; j < i; j++)
            {
                printf("*(x");
                if (x[j] < 0)
                    printf("+");
                printf("%.2f)", -x[j]);
            }
            if (i < n && z[i + 1] >= 0)
            {
                printf("+");
            }
        }
        printf("\n");
    }
    //输出导数
    void printderivative()
    {
        for (int i = 1; i <= n; i++)
        {
            if (i == 1)
            {
                printf("%f+", z[i]);
                continue;
            }
            printf("%f*(", z[i]);
            for (int j = 0; j < i; j++)
            {
                for (int k = 0; k < i; k++)
                {
                    if (k != j)
                    {
                        printf("(x-%.1f)", x[k]);
                        if (j < i - 1 && k < i - 1)
                            printf("*");
                        else if (j == i - 1 && k < i - 2)
                            printf("*");
                    }
                }
                if (j < i - 1)
                    printf("+");
            }
            printf(")");
            if (i < n && z[i + 1] >= 0)
            {
                printf("+");
            }
        }
    }
};

//把数组输入进向量
void pushback(vector<double> &x, double a[], int n)
{
    x.clear();
    for (int i = 0; i < n; i++)
        x.push_back(a[i]);
}

#endif